#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int from, to, cost;
};

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.cost < e2.cost;
}

int find(vector<int>& parent, int i) {
    if (parent[i] == -1) {
        return i;
    }
    return find(parent, parent[i]);
}

void unionSets(vector<int>& parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

int minCostToConnectAllPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<Edge> edges;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
            edges.push_back({i, j, cost});
        }
    }
        sort(edges.begin(), edges.end(), compareEdges);
    vector<int> parent(n, -1);

    int minCost = 0;
    for (const Edge& edge : edges) {
        int x = find(parent, edge.from);
        int y = find(parent, edge.to);
        if (x != y) {
            minCost += edge.cost;
            unionSets(parent, x, y);
        }
    }

    return minCost;
}

int main() {
    vector<vector<int>> points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
    int result = minCostToConnectAllPoints(points);
    cout << "链接所有点的最小费用为：" << result << endl;
    return 0;
}
